package medium

import "sort"

/*
时间复杂度:O(NlogN)
空间复杂度:O(logN)

难点:如何判断多个范围间有重叠区间
解决:如果先根据左边界排序,然后判断后面的左边界<=前面的范围的右边界,可以判断两个区间之间是重叠的,但是会有一个问题,例如:
	[1,10] [2,4] [6,8];  [2,4]与[6,8]确实与[1,10]重叠,但是[2,4]与[6,8]不重叠,所以这样判断多个范围重叠时是错误的

正确方法: 先根据右边界排序,如果后面范围的左边界<=前面范围的右边界,则表示前面范围的后半部分与后面范围的前半部分一定有重叠;
	这样就可以判断多个范围是否同时存在重叠部分
*/

func findMinArrowShots(points [][]int) int {
	// 1.按照右边界排序
	sort.Slice(points, func(i, j int) bool {
		return points[i][1] < points[j][1]
	})
	count := 1
	// 2.遍历points,记录maxRights,如果后范围的左边界>maxRight 说明出现了不重叠区间,则更新maxRight为新的区间的右边界
	maxRight := points[0][1]
	for _, p := range points {
		if p[0] > maxRight {
			maxRight = p[1]
			count++
		}
	}
	return count
}
